
/*
*  Based on the B+ Tree Implementation by 
*  Amittai Aviram  amittai.aviram@yale.edu
*  (version 1.4)
*
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

#include "bpt.h"

// FUNCTION PROTOTYPES.

// Output and utility.

static int cut( int length );

// Insertion.

static record * make_record(int value);
static node * make_node( void );
static node * make_leaf( void );
static int get_left_index(node * parent, node * left);
static node * insert_into_leaf( node * leaf, int key, record * pointer );
static node * insert_into_leaf_after_splitting(node * root, node * leaf, int key, record * pointer);
static node * insert_into_node(node * root, node * parent, int left_index, int key, node * right);
static node * insert_into_node_after_splitting(node * root, node * parent, int left_index, int key, node * right);
static node * insert_into_parent(node * root, node * left, int key, node * right);
static node * insert_into_new_root(node * left, int key, node * right);

// Deletion.

static int get_neighbor_index( node * n );
static node * adjust_root(node * root);
static node * coalesce_nodes(node * root, node * n, node * neighbor, int neighbor_index, int k_prime);
static node * redistribute_nodes(node * root, node * n, node * neighbor, int neighbor_index, int k_prime_index, int k_prime);
static node * delete_entry( node * root, node * n, int key, void * pointer );


/* Traces the path from the root to a leaf, searching
* by key.  Displays information about the path
* if the verbose flag is set.
* Returns the leaf containing the given key.
*/
static node * find_leaf( node * root, int key ) {
	int i = 0;
	node * c = root;
	if (c == NULL) {
		return c;
	}
	while (!c->is_leaf) {
		i = 0;
		while (i < c->num_keys) {
			if (key >= c->keys[i]) i++;
			else break;
		}
		c = (node *)c->pointers[i];
	}
	return c;
}

/* Finds and returns the record to which
* a key refers.
*/
record * find( node * root, int key ) {
	int i = 0;
	node * c = find_leaf( root, key );
	if (c == NULL) return NULL;
	for (i = 0; i < c->num_keys; i++)
		if (c->keys[i] == key) break;
	if (i == c->num_keys) 
		return NULL;
	else
		return (record *)c->pointers[i];
}

/* Finds the appropriate place to
* split a node that is too big into two.
*/
static int cut( int length ) {
	if (length % 2 == 0)
		return length/2;
	else
		return length/2 + 1;
}













// INSERTION

static node * allocate_node() {
	node * new_node = malloc(sizeof(node));
	assert(new_node != NULL);
	return new_node;
}

static void free_node(node * n) {
	assert(n != NULL);
	free(n);
}


/* Creates a new record to hold the value
* to which a key refers.
*/
static record * make_record(int value) {
	record * new_record = (record *)malloc(sizeof(record));
	assert(new_record != NULL);

	new_record->value = value;
	return new_record;
}


/* Creates a new general node, which can be adapted
* to serve as either a leaf or an internal node.
*/
static node * make_node( void ) {
	node * new_node = allocate_node();
	new_node->is_leaf = false;
	new_node->num_keys = 0;
	new_node->parent = NULL;
	new_node->next = NULL;
	return new_node;
}

/* Creates a new leaf by creating a node
* and then adapting it appropriately.
*/
static node * make_leaf( void ) {
	node * leaf = make_node();
	leaf->is_leaf = true;
	return leaf;
}


/* Helper function used in insert_into_parent
* to find the index of the parent's pointer to 
* the node to the left of the key to be inserted.
*/
static int get_left_index(node * parent, node * left) {

	int left_index = 0;
	while (left_index <= parent->num_keys && 
		parent->pointers[left_index] != left)
		left_index++;
	return left_index;
}

/* Inserts a new pointer to a record and its corresponding
* key into a leaf.
* Returns the altered leaf.
*/
static node * insert_into_leaf( node * leaf, int key, record * pointer ) {

	int i, insertion_point;

	insertion_point = 0;
	while (insertion_point < leaf->num_keys && leaf->keys[insertion_point] < key)
		insertion_point++;

	for (i = leaf->num_keys; i > insertion_point; i--) {
		leaf->keys[i] = leaf->keys[i - 1];
		leaf->pointers[i] = leaf->pointers[i - 1];
	}
	leaf->keys[insertion_point] = key;
	leaf->pointers[insertion_point] = pointer;
	leaf->num_keys++;
	return leaf;
}


/* Inserts a new key and pointer
* to a new record into a leaf so as to exceed
* the tree's order, causing the leaf to be split
* in half.
*/
static node * insert_into_leaf_after_splitting(node * root, node * leaf, int key, record * pointer) {

	node * new_leaf;
	int insertion_index, split, new_key, i, j;

	new_leaf = make_leaf();

	static record * temp_pointers[(BPT_ORDER + 1)];
	static int temp_keys[BPT_ORDER];

	insertion_index = 0;
	while (leaf->keys[insertion_index] < key && insertion_index < BPT_ORDER - 1)
		insertion_index++;

	for (i = 0, j = 0; i < leaf->num_keys; i++, j++) {
		if (j == insertion_index) j++;
		temp_keys[j] = leaf->keys[i];
		temp_pointers[j] = leaf->pointers[i];
	}

	temp_keys[insertion_index] = key;
	temp_pointers[insertion_index] = pointer;

	leaf->num_keys = 0;

	split = cut(BPT_ORDER - 1);

	for (i = 0; i < split; i++) {
		leaf->pointers[i] = temp_pointers[i];
		leaf->keys[i] = temp_keys[i];
		leaf->num_keys++;
	}

	for (i = split, j = 0; i < BPT_ORDER; i++, j++) {
		new_leaf->pointers[j] = temp_pointers[i];
		new_leaf->keys[j] = temp_keys[i];
		new_leaf->num_keys++;
	}

	new_leaf->pointers[BPT_ORDER - 1] = leaf->pointers[BPT_ORDER - 1];
	leaf->pointers[BPT_ORDER - 1] = new_leaf;

	for (i = leaf->num_keys; i < BPT_ORDER - 1; i++)
		leaf->pointers[i] = NULL;
	for (i = new_leaf->num_keys; i < BPT_ORDER - 1; i++)
		new_leaf->pointers[i] = NULL;

	new_leaf->parent = leaf->parent;
	new_key = new_leaf->keys[0];

	return insert_into_parent(root, leaf, new_key, new_leaf);
}


/* Inserts a new key and pointer to a node
* into a node into which these can fit
* without violating the B+ tree properties.
*/
static node * insert_into_node(node * root, node * n, 
int left_index, int key, node * right) {
	int i;

	for (i = n->num_keys; i > left_index; i--) {
		n->pointers[i + 1] = n->pointers[i];
		n->keys[i] = n->keys[i - 1];
	}
	n->pointers[left_index + 1] = right;
	n->keys[left_index] = key;
	n->num_keys++;
	return root;
}


/* Inserts a new key and pointer to a node
* into a node, causing the node's size to exceed
* the order, and causing the node to split into two.
*/
static node * insert_into_node_after_splitting(node * root, node * old_node, int left_index, 
int key, node * right) {

	int i, j, split, k_prime;
	node * new_node, * child;

/* First create a temporary set of keys and pointers
 * to hold everything in order, including
 * the new key and pointer, inserted in their
 * correct places. 
 * Then create a new node and copy half of the 
 * keys and pointers to the old node and
 * the other half to the new.
 */

	static node * temp_pointers[BPT_ORDER + 1];
	static int temp_keys[BPT_ORDER];

	for (i = 0, j = 0; i < old_node->num_keys + 1; i++, j++) {
		if (j == left_index + 1) j++;
		temp_pointers[j] = old_node->pointers[i];
	}

	for (i = 0, j = 0; i < old_node->num_keys; i++, j++) {
		if (j == left_index) j++;
		temp_keys[j] = old_node->keys[i];
	}

	temp_pointers[left_index + 1] = right;
	temp_keys[left_index] = key;

/* Create the new node and copy
* half the keys and pointers to the
* old and half to the new.
*/  
	split = cut(BPT_ORDER);
	new_node = make_node();
	old_node->num_keys = 0;
	for (i = 0; i < split - 1; i++) {
		old_node->pointers[i] = temp_pointers[i];
		old_node->keys[i] = temp_keys[i];
		old_node->num_keys++;
	}
	old_node->pointers[i] = temp_pointers[i];
	k_prime = temp_keys[split - 1];
	for (++i, j = 0; i < BPT_ORDER; i++, j++) {
		new_node->pointers[j] = temp_pointers[i];
		new_node->keys[j] = temp_keys[i];
		new_node->num_keys++;
	}
	new_node->pointers[j] = temp_pointers[i];
	new_node->parent = old_node->parent;
	for (i = 0; i <= new_node->num_keys; i++) {
		child = new_node->pointers[i];
		child->parent = new_node;
	}

/* Insert a new key into the parent of the two
* nodes resulting from the split, with
* the old node to the left and the new to the right.
*/

	return insert_into_parent(root, old_node, k_prime, new_node);
}



/* Inserts a new node (leaf or internal node) into the B+ tree.
* Returns the root of the tree after insertion.
*/
static node * insert_into_parent(node * root, node * left, int key, node * right) {

	int left_index;
	node * parent;

	parent = left->parent;

/* Case: new root. */

	if (parent == NULL)
		return insert_into_new_root(left, key, right);

/* Case: leaf or node. (Remainder of
* function body.)  
*/

/* Find the parent's pointer to the left 
* node.
*/

	left_index = get_left_index(parent, left);


/* Simple case: the new key fits into the node. 
*/

	if (parent->num_keys < BPT_ORDER - 1)
		return insert_into_node(root, parent, left_index, key, right);

/* Harder case:  split a node in order 
* to preserve the B+ tree properties.
*/

	return insert_into_node_after_splitting(root, parent, left_index, key, right);
}


/* Creates a new root for two subtrees
* and inserts the appropriate key into
* the new root.
*/
static node * insert_into_new_root(node * left, int key, node * right) {

	node * root = make_node();
	root->keys[0] = key;
	root->pointers[0] = left;
	root->pointers[1] = right;
	root->num_keys++;
	root->parent = NULL;
	left->parent = root;
	right->parent = root;
	return root;
}



/* First insertion:
* start a new tree.
*/
node * start_new_tree(int key, record * pointer) {

	node * root = make_leaf();
	root->keys[0] = key;
	root->pointers[0] = pointer;
	root->pointers[BPT_ORDER - 1] = NULL;
	root->parent = NULL;
	root->num_keys++;
	return root;
}



/* Master insertion function.
* Inserts a key and an associated value into
* the B+ tree, causing the tree to be adjusted
* however necessary to maintain the B+ tree
* properties.
*/
node * insert( node * root, int key, int value ) {

	record * pointer;
	node * leaf;

/* The current implementation ignores
* duplicates.
*/

	if (find(root, key) != NULL)
	return root;

/* Create a new record for the
* value.
*/
	pointer = make_record(value);


/* Case: the tree does not exist yet.
* Start a new tree.
*/

	if (root == NULL) 
	return start_new_tree(key, pointer);


/* Case: the tree already exists.
* (Rest of function body.)
*/

	leaf = find_leaf(root, key);

/* Case: leaf has room for key and pointer.
*/

	if (leaf->num_keys < BPT_ORDER - 1) {
		leaf = insert_into_leaf(leaf, key, pointer);
		return root;
	}


/* Case:  leaf must be split.
*/

	return insert_into_leaf_after_splitting(root, leaf, key, pointer);
}




// DELETION.

/* Utility function for deletion.  Retrieves
* the index of a node's nearest neighbor (sibling)
* to the left if one exists.  If not (the node
* is the leftmost child), returns -1 to signify
* this special case.
*/
static int get_neighbor_index( node * n ) {

	int i;

/* Return the index of the key to the left
* of the pointer in the parent pointing
* to n.  
* If n is the leftmost child, this means
* return -1.
*/
	for (i = 0; i <= n->parent->num_keys; i++) {
		if (n->parent->pointers[i] == n) {
			return i - 1;			
		}
	}

// Error state.
	printf("Search for nonexistent pointer to node in parent.\n");
	printf("Node:  %#x\n", (unsigned int)n);
	assert(1 == 0);
}


static node * remove_entry_from_node(node * n, int key, node * pointer) {

	int i, num_pointers;

// Remove the key and shift other keys accordingly.
	i = 0;
	while (n->keys[i] != key)
		i++;
	for (++i; i < n->num_keys; i++)
		n->keys[i - 1] = n->keys[i];

// Remove the pointer and shift other pointers accordingly.
// First determine number of pointers.
	num_pointers = n->is_leaf ? n->num_keys : n->num_keys + 1;
	i = 0;
	while (n->pointers[i] != pointer)
		i++;
	for (++i; i < num_pointers; i++)
		n->pointers[i - 1] = n->pointers[i];


// One key fewer.
	n->num_keys--;

// Set the other pointers to NULL for tidiness.
// A leaf uses the last pointer to point to the next leaf.
	if (n->is_leaf)
		for (i = n->num_keys; i < BPT_ORDER - 1; i++)
		n->pointers[i] = NULL;
	else
		for (i = n->num_keys + 1; i < BPT_ORDER; i++)
		n->pointers[i] = NULL;

	return n;
}


static node * adjust_root(node * root) {

	node * new_root;

/* Case: nonempty root.
* Key and pointer have already been deleted,
* so nothing to be done.
*/

	if (root->num_keys > 0) {
		return root;
	}

/* Case: empty root. 
*/

// If it has a child, promote 
// the first (only) child
// as the new root.

	if (!root->is_leaf) {
		new_root = root->pointers[0];
		new_root->parent = NULL;
	}

// If it is a leaf (has no children),
// then the whole tree is empty.

	else { 
		new_root = NULL;
	}
	free_node(root);

	return new_root;
}


/* Coalesces a node that has become
* too small after deletion
* with a neighboring node that
* can accept the additional entries
* without exceeding the maximum.
*/
static node * coalesce_nodes(node * root, node * n, node * neighbor, int neighbor_index, int k_prime) {

	int i, j, neighbor_insertion_index, n_start, n_end, new_k_prime = 0;
	node * tmp;
	bool split;

/* Swap neighbor with node if node is on the
* extreme left and neighbor is to its right.
*/

	if (neighbor_index == -1) {
		tmp = n;
		n = neighbor;
		neighbor = tmp;
	}

/* Starting point in the neighbor for copying
* keys and pointers from n.
* Recall that n and neighbor have swapped places
* in the special case of n being a leftmost child.
*/

	neighbor_insertion_index = neighbor->num_keys;

/*
* Nonleaf nodes may sometimes need to remain split,
* if the insertion of k_prime would cause the resulting
* single coalesced node to exceed the limit order - 1.
* The variable split is always false for leaf nodes
* and only sometimes set to true for nonleaf nodes.
*/

	split = false;

/* Case:  nonleaf node.
* Append k_prime and the following pointer.
* If there is room in the neighbor, append
* all pointers and keys from the neighbor.
* Otherwise, append only cut(order) - 2 keys and
* cut(order) - 1 pointers.
*/

	if (!n->is_leaf) {

	/* Append k_prime.
	*/

		neighbor->keys[neighbor_insertion_index] = k_prime;
		neighbor->num_keys++;


	/* Case (default):  there is room for all of n's keys and pointers
	* in the neighbor after appending k_prime.
	*/

		n_end = n->num_keys;

	/* Case (special): k cannot fit with all the other keys and pointers
	* into one coalesced node.
	*/
		n_start = 0; // Only used in this special case.
		if (n->num_keys + neighbor->num_keys >= BPT_ORDER) {
			split = true;
			n_end = cut(BPT_ORDER) - 2;
		}

		for (i = neighbor_insertion_index + 1, j = 0; j < n_end; i++, j++) {
			neighbor->keys[i] = n->keys[j];
			neighbor->pointers[i] = n->pointers[j];
			neighbor->num_keys++;
			n->num_keys--;
			n_start++;
		}

	/* The number of pointers is always
	* one more than the number of keys.
	*/

		neighbor->pointers[i] = n->pointers[j];

	/* If the nodes are still split, remove the first key from
	* n.
	*/
		if (split) {
			new_k_prime = n->keys[n_start];
			for (i = 0, j = n_start + 1; i < n->num_keys; i++, j++) {
				n->keys[i] = n->keys[j];
				n->pointers[i] = n->pointers[j];
			}
			n->pointers[i] = n->pointers[j];
			n->num_keys--;
		}

	/* All children must now point up to the same parent.
	*/

		for (i = 0; i < neighbor->num_keys + 1; i++) {
			tmp = (node *)neighbor->pointers[i];
			tmp->parent = neighbor;
		}
	}

/* In a leaf, append the keys and pointers of
* n to the neighbor.
* Set the neighbor's last pointer to point to
* what had been n's right neighbor.
*/

	else {
		for (i = neighbor_insertion_index, j = 0; j < n->num_keys; i++, j++) {
			neighbor->keys[i] = n->keys[j];
			neighbor->pointers[i] = n->pointers[j];
			neighbor->num_keys++;
		}
		neighbor->pointers[BPT_ORDER - 1] = n->pointers[BPT_ORDER - 1];
	}

	if (!split) {
		root = delete_entry(root, n->parent, k_prime, n);
		free_node(n); 
	}
	else {
		for (i = 0; i < n->parent->num_keys; i++) {
			if (n->parent->pointers[i + 1] == n) {
				n->parent->keys[i] = new_k_prime;
				break;
			}
		}
	}

	return root;

}


/* Redistributes entries between two nodes when
* one has become too small after deletion
* but its neighbor is too big to append the
* small node's entries without exceeding the
* maximum
*/
static node * redistribute_nodes(node * root, node * n, node * neighbor, int neighbor_index, 
int k_prime_index, int k_prime) {  

	int i;
	node * tmp;

/* Case: n has a neighbor to the left. 
* Pull the neighbor's last key-pointer pair over
* from the neighbor's right end to n's left end.
*/

	if (neighbor_index != -1) {
		if (!n->is_leaf)
			n->pointers[n->num_keys + 1] = n->pointers[n->num_keys];
		for (i = n->num_keys; i > 0; i--) {
			n->keys[i] = n->keys[i - 1];
			n->pointers[i] = n->pointers[i - 1];
		}
		if (!n->is_leaf) {
			n->pointers[0] = neighbor->pointers[neighbor->num_keys];
			tmp = (node *)n->pointers[0];
			tmp->parent = n;
			neighbor->pointers[neighbor->num_keys] = NULL;
			n->keys[0] = k_prime;
			n->parent->keys[k_prime_index] = neighbor->keys[neighbor->num_keys - 1];
		}
		else {
			n->pointers[0] = neighbor->pointers[neighbor->num_keys - 1];
			neighbor->pointers[neighbor->num_keys - 1] = NULL;
			n->keys[0] = neighbor->keys[neighbor->num_keys - 1];
			n->parent->keys[k_prime_index] = n->keys[0];
		}
	}

/* Case: n is the leftmost child.
* Take a key-pointer pair from the neighbor to the right.
* Move the neighbor's leftmost key-pointer pair
* to n's rightmost position.
*/

	else {  
		n->keys[n->num_keys] = k_prime;
		if (n->is_leaf)
			n->pointers[n->num_keys] = neighbor->pointers[0];
		else {
			n->pointers[n->num_keys + 1] = neighbor->pointers[0];
			tmp = (node *)n->pointers[n->num_keys + 1];
			tmp->parent = n;
		}
		n->parent->keys[k_prime_index] = neighbor->keys[0];
		for (i = 0; i < neighbor->num_keys; i++) {
			neighbor->keys[i] = neighbor->keys[i + 1];
			neighbor->pointers[i] = neighbor->pointers[i + 1];
		}
		if (!n->is_leaf)
			neighbor->pointers[i] = neighbor->pointers[i + 1];
	}

/* n now has one more key and one more pointer;
* the neighbor has one fewer of each.
*/

	n->num_keys++;
	neighbor->num_keys--;

	return root;
}


/* Deletes an entry from the B+ tree.
* Removes the record and its key and pointer
* from the leaf, and then makes all appropriate
* changes to preserve the B+ tree properties.
*/
static node * delete_entry( node * root, node * n, int key, void * pointer ) {

	int min_keys;
	node * neighbor;
	int neighbor_index;
	int k_prime_index, k_prime;
	int capacity;

// Remove key and pointer from node.

	n = remove_entry_from_node(n, key, pointer);

/* Case:  deletion from the root. 
*/

	if (n == root) 
		return adjust_root(root);


/* Case:  deletion from a node below the root.
* (Rest of function body.)
*/

/* Determine minimum allowable size of node,
* to be preserved after deletion.
*/

	min_keys = n->is_leaf ? cut(BPT_ORDER - 1) : cut(BPT_ORDER) - 1;

/* Case:  node stays at or above minimum.
* (The simple case.)
*/

	if (n->num_keys >= min_keys) {
		return root;
	}
/* Case:  node falls below minimum.
* Either coalescence or redistribution
* is needed.
*/

/* Find the appropriate neighbor node with which
* to coalesce.
* Also find the key (k_prime) in the parent
* between the pointer to node n and the pointer
* to the neighbor.
*/

	neighbor_index = get_neighbor_index( n );
	k_prime_index = neighbor_index == -1 ? 0 : neighbor_index;
	k_prime = n->parent->keys[k_prime_index];
	neighbor = neighbor_index == -1 ? n->parent->pointers[1] : 
	n->parent->pointers[neighbor_index];

	capacity = n->is_leaf ? BPT_ORDER : BPT_ORDER - 1;

/* Coalescence. */

	if (neighbor->num_keys + n->num_keys < capacity) {
		return coalesce_nodes(root, n, neighbor, neighbor_index, k_prime);		
	}

/* Redistribution. */

	else {
		return redistribute_nodes(root, n, neighbor, neighbor_index, k_prime_index, k_prime);		
	}
}



/* Master deletion function.
*/
node * delete(node * root, int key) {

	node * key_leaf;
	record * key_record;

	key_record = find(root, key);
	key_leaf = find_leaf(root, key);
	if (key_record != NULL && key_leaf != NULL) {
		free(key_record);
		root = delete_entry(root, key_leaf, key, key_record);
	}
	return root;
}


static void destroy_tree_nodes(node * root) {
	int i;
	if (root->is_leaf)
		for (i = 0; i < root->num_keys; i++)
		free_node(root->pointers[i]);
	else
		for (i = 0; i < root->num_keys + 1; i++)
		destroy_tree_nodes(root->pointers[i]);
	free_node(root);
}


node * destroy_tree(node * root) {
	destroy_tree_nodes(root);
	return NULL;
}

void print_stats( void ) {
	printf("-----------------------------------------\n");
	printf("Btree degree:%d\n", BPT_ORDER);
	printf("Node size: %u bytes\n", (unsigned)sizeof(node));
	printf("Record size: %u bytes\n", (unsigned)sizeof(record));
	
	unsigned h;
	unsigned num_leaves = 1;
	unsigned num_nodes = 1;
	unsigned max_records = BPT_ORDER-1;
	unsigned min_records = 1;
	unsigned d_power_of_h = BPT_ORDER;
	
	for(h = 1; h <= 5; ++h) {
		
		printf("Height:%u\n", h);
		printf("  Max number of nodes: %u", num_nodes);
		printf("  (of which %u leaves)\n", num_leaves);
		printf("  Number of records: [%u...%u]\n", min_records, max_records);
		
		num_leaves = d_power_of_h; //d^(h-1)
		num_nodes += d_power_of_h; //d^(h-1) + d^(h-2) + ... + 1
		d_power_of_h *= BPT_ORDER; //d^h
		max_records = d_power_of_h - num_leaves; //d^(h) - d^(h-1)
		min_records *= cut(BPT_ORDER); //(d/2)^(h-1)
	}
	printf("-----------------------------------------\n");
		
}